Amiga Mag HDD Backup/Amiga Mag HDD Backup.zip/Amiga Mag HDD Backup/Alexander.img.bin/Alexander.img/tech 4.1 editorial Archive.sit/Griebling/HUGE Numbers (Part 1)

Text File | 1993-06-16 | 17KB | 321 lines

HUGE NUMBERS


Introduction

This series of three articles explores an alternate floating point number
system (called Extended Precision Numbers or ExNumbers) which allows an almost
unlimited number of digits and can exactly represent all decimal fractions.

To demonstrate a practical use of ExNumbers, a scientific calculator is
incrementally developed so that each article adds a major new capability. The
final calculator has support for logical, transcendental, logarithmic, and
exponential operations and is implemented as a Workbench-compatible tool, with
either mouse-driven or keypad entry of complete equations.

This article introduces the ExNumbers, describes utilities such as comparison
of two numbers, absolute value, digit shifting, and multiplication/division by
ten, and develops the basic operations of addition, subtraction,
multiplication, and division.  Next, various conversions to/from ExNumbers are
covered.  Finally, there is a brief tour of the initial CLI-based calculator to
demonstrate the power of ExNumbers in a real application.


Amiga Math Problems

The Amiga has an almost embarrassing abundance of floating point math
libraries which include the Fast Floating Point (FFP) library, IEEE 32-bit
and IEEE 64-bit floating point libraries.  The latter two are supported by the
Amiga's floating point coprocessor.  But there are serious deficiencies in all
of these numerical representations.

The chief problem with these floating point formats is that they are encoded as
binary numbers (mathematical base 2) while we tend more naturally to decimal
numbers (base 10).  As a consequence, the fractional representations of the
binary numbers are usually slightly different from the decimal number fractions
that we would expect.  For example, the number 0.8 is exactly representable as
a decimal number while the closest binary fraction, in IEEE 32-bit format, ends
up being 0.799999952316284.  This difference is very important to business
people who can't get their spreadsheets to balance when accumulated round-off
errors don't balance out to zero.  ExNumbers can represent all decimal
fractions exactly so no pennies are gained or lost.

A second problem is that the maximum resolution supported by the IEEE 64-bit
format is only about 15 digits.  This limitation may be very serious to
very large corporations whose accumulated income is numbered in billions of
dollars and to space explorers who need to send a space probe to an exact
orbital position.  With a virtually unlimited number of digits, ExNumbers can
again meet the need for higher resolutions.

There is a down side to the use of ExNumbers.  Since they are implemented in
software, they are slower than coprocessor-based floating point numbers for
an equivalent number of digits.  Certainly, when using many digits, the
calculations are slower.  In the proposed calculator application, however,
the slower speed is not noticeable.


Structure of ExNumbers

ExNumbers are represented as an array of 16-bit signed words, each of which
contains four decimal digits and is called a Quad.  The exponent is
kept in a separate 16-bit word; and the number's sign is an enumeration of
`positive' and `negative' values (Figure 1).

ExNumber Quads are different from Binary-Coded Decimal (BCD) representations
which are also used to store decimal-encoded numbers.  The Quads actually
encode four decimal digits using a binary number so they are stored more
efficiently and are faster than BCD numbers in calculations.

For example, to encode 123456.789 as an ExNumber, we first need to normalize
this number to a value whose mantissa is between -10 and 10.  In other words,
the number is represented in scientific notation as 1.23456789E6.  Next, this
number is broken into groups of four digits, beginning at the leftmost digit.
The decomposed number can now be represented as 1234 5678 9000 E0006 where the
E0006 is the number's exponent.  Note the trailing zeros in the 9000 Quad.
These extra digit place holders are required to pad this Quad because, if they
were omitted, the final 9 would be interpreted as 0009 which would lead to the
erroneous number 123456.780009.  The three Quads from this example are stored
in binary form as shown in Figure 1.

<INSERT FIGURE 1 HERE>


Utilities

Before dealing with the main mathematical operations, I need to introduce a few
utilities which will be used in these algorithms.

The first of these is the ExCompare function which produces a result to
indicate whether one ExNumber is equal to, greater than, or less than another
ExNumber.  Although the algorithm in Listing 1 for ExCompare appears confusing,
Table 1 summarizes the decisions which are used to produce an ExNumber
comparison.  The notation A(+) indicates that A is positive, Aexp is an
abbreviation for A's exponent, and A(i) represents the ith Quad
of A.

<INSERT TABLE 1 HERE>

The ExChgSign procedure negates a number which means that the sign is toggled
from positive to negative and vice versa.

ExAbs takes the absolute value of a number by forcing the sign to be positive.

ExNorm normalizes an ExNumber by removing leading zeros in a fraction and
adjusting the exponent to guarantee a mantissa between -10 and 10.  For
example, 0.0000456 would be normalized to 4.56E-6.

ExTimes10 increments the exponent by 1 to simulate a multiplication by 10.
This procedure is much faster than really multiplying an ExNumber by 10.

Similarly, ExDiv10 subtracts 1 from the exponent to simulate a division by
10.  This procedure is also much faster than attempting to divide an ExNumber
by 10.

The ExShiftRight procedure is used for shifting a single digit rightmost into
an ExNumber's mantissa.  Shifting 8 into the number 6.7892 produces the number
8.67892.

ExShiftLeft shifts an ExNumber to the left by a single digit and replaces the
least significant digit with a zero.

The IsZero function returns true if the ExNumber argument passed to it is equal
to zero.


Basic Arithmetic

Some of us may remember how confusing it was when first learning about binary
numbers after having been exposed for most of our lives to decimal numbers.
Well, the bad news is that you can forget most of what you learned about binary
arithmetic; the good news is that the basic ExNumber operations of addition,
subtraction, multiplication, and division are performed in very much the same
way that we are used to from our daily lives.

Addition is the most basic operation in the ExNumbers module (Listing 1) and
the ExAddUtility is the heart of the addition algorithm which is used by the
exported ExAdd procedure.  Two positive numbers are added together in three
steps: first, set the exponent of the result to the exponent of the larger
number; second, shift the smaller number so that its Quads are aligned with the
larger number; and finally, add together all the related Quads.  The example in
Figure 2 illustrates how the numbers 1.2345678E9 and 3.21456E5 are added
together.

<INSERT FIGURE 2 HERE>

The ExSubUtility subtracts two numbers using almost the same steps also used by
the ExAddUtility with the exception that Quads are subtracted from each other
instead of being added.

To simplify both addition and subtraction algorithms, I made a tacit assumption
that both numbers would be positive.  The reason this works is seen in how the
ExAdd procedure checks and manipulates the signs of the two numbers to be added
together.  There are two possibilities: both numbers have the same sign (either
positive or negative) so they can be added together using the ExAddUtility
procedure; or the numbers have different signs so we subtract the negative
number from the positive number using the ExSubUtility procedure.

The ExSub procedure is even simpler.  This algorithm makes use of the
well-known property that B - C can be rewritten as B + (-C).  Thus, by negating
C, a call to the ExAdd procedure produces the correct answer.

ExMult multiplies two ExNumbers together using the same techniques that we were
taught in school.  Two nested loops produce a product by using the outer loop
to index the first number's ith Quad and then the inner loop multiplies this
Quad by each of the Quads in the second number to produce an intermediate
product.  Any carries are then shifted into this intermediate product, the
exponent is adjusted accordingly, and the intermediate product is added to the
final result.  The above process is repeated until an intermediate product has
been produced and added to the final result for each Quad in the first number.
Figure 3 demonstrates the multiplication of 1.2345678E5 and 9.8765432E10.

<INSERT FIGURE 3 HERE>

The division algorithm should also be familiar to everyone.  First, the
result's exponent is calculated by subtracting the divisor's exponent from the
dividend's exponent.  Next, the divisor and dividend are normalized and they
are forced to be positive numbers.  This step is equivalent to lining up the
divisor and dividend prior to beginning a manual division.  Once again, two
nested loops are used but now the outer loop iterates over all the digits in an
ExNumber while the inner loop increments a quotient counter and subtracts the
divisor from the dividend as long as the dividend is greater than or equal to
the divisor.  This is roughly what we do when manually comparing the divisor
with the dividend and estimate a quotient which when multiplied by the divisor
and subtracted from the dividend leaves the dividend less than the divisor. Our
algorithm here, however, replaces the multiplication/subtraction step with
just a series of subtractions.  Finally, the divisor is divided by 10 to shift
it within the range of the dividend for the next digit of the quotient and the
whole process repeats.  The division algorithm's outer loop guarantees that
enough quotient digits are produced to fill all the ExNumber Quads.  Figure 4
takes you through the steps involved in dividing 3.550E2 by 1.130E2.

<INSERT FIGURE 4 HERE>


String Conversions

Before getting on to the actual calculator project, a couple of procedures are
still missing.  We need a way of translating a string into an ExNumber and,
conversely, producing a string from an ExNumber.

The StrToExNum procedure accomplishes the first of our goals.  This algorithm
parses a string into a set of digits (0-9), signs (+, -), and punctuation (.,
E).  First, leading spaces are stripped off and the sign of the number is
determined.  Then, as each digit is encountered, it is packed into a Quad at a
position just to the right of the previous digit.  The ExNumber's Quads are
indexed by a digit counter which is also used to let us know when enough digits
have been gathered.  An exponent counter is incremented for each digit in the
number. When reaching the digit maximum, only the exponent counter continues to
be incremented but no more digits are added to the ExNumber. When a decimal is
reached, the exponent counter increments are stopped.  If an `E' (exponent) is
encountered, the ExNumber's mantissa is considered complete and the exponent's
sign is determined.  All following digits are merged into the ExNumber's
exponent to which the exponent counter is either added or subtracted--depending
on whether the exponent is positive or negative.

The second conversion routine, ExNumToStr, produces a character string from an
ExNumber.  Two different floating point number formats are supported:
scientific notation (e.g., 1.23E10) and floating point notation (e.g.,
234.234).  Floating point notation is used whenever the ExNumber is small
enough to be represented in a field of `MaxDigits', which represents the
maximum number of digits selected by the user. Both conversions begin by
checking the sign of the ExNumber and inserting a minus sign if the number is
negative.

The scientific notation conversion continues by rounding the ExNumber to the
number of decimal places specified by the `Decimal' argument.  The leftmost
digit is then inserted into the string, followed by a decimal point.  Exactly
`Decimal' digits are placed after the decimal point (even if they are all
zeros).  The exponent symbol, `E', is added to the output string, followed by
the exponent's sign.  A Modula-2 library function called ConvNumToStr, which
converts integers into strings, is then used to convert the exponent into a
string which is appended at the end of the output string.

Converting ExNumbers into floating point notation is a bit more complicated.
As before, the number is rounded to maximum number of digits--in this case, the
exponent size plus the number of specified decimal places.  If the ExNumber is
less than zero, a leading `0.' is placed in the string, followed by enough
zeros to reduce the number's exponent to zero.  Next, enough digits are placed
into the output string to satisfy the requested number of decimal places or
exhaust the total number of digits in an ExNumber, whichever comes first.
While placing these digits in the output string, a counter (InCnt) also keeps
track of the decimal point so it can be placed at the right place in the output
string.  The last step of the conversion process removes trailing zeros from
numbers like 35.123000000 to give more readable numbers like 35.123.


The CLI Calculator

Listing 2 gives the complete calculator source code which supports the basic
mathematical operations covered in this article.  The calculator is implemented
with a very basic tokenizer (GetToken), which takes a stream of input
characters and translates them into the set of tokens identified at the top of
Listing 2 following the `Tokens' type.  Quite a few more tokens are identified
than are being used in this first calculator version but this complete list
should give a tantalizing view of the features which will be added in the next
article.

The stream of tokens drive a simple recursive expression evaluator (Expression)
which accepts prioritized infix notation with bracketing limited only by stack
size and input string length restrictions (250 characters).  Operators are
ordered as follows:
Highest priority (reciprocal, squared), Medium priority (times, divide), Lowest
priority (plus, minus, negate, and unary plus).  Thus, an expression like 2 + 5
* 6 would give the expected result of 32, and not 42.

The calculator also supports `friendly' number entry which allows numbers to
contain punctuation characters like commas, apostrophes, and underscores which
can be used to separate groups of digits (e.g., 5,000 and 1'000'000.45).  This
feature is especially useful with 50-digit numbers!


A Sample Session

To use the calculator, make sure you either are in the directory which contains
the calculator program or copy the calculator into a directory which is part
of your regular command path.  Type `Calculator' from the CLI and you are
greeted with a `CALC>' prompt.  Simply type in the following equation exactly
as it appears (hold down the ALT key and press `2' to get the ▓ character and
similarly to get the ¡╣ hold the ALT key and press `N', then `1'), and
enter a Return:

4 * Pi * (89.234 + 4E1 / 2.0)▓ - (2-╣ * 56.78 * 10)

The answer 149658.8731 appears on the next line after the equation.  Note the
use of the name `Pi' to represent the mathematical quantity 3.141592..., the
squared operator (▓), and the reciprocal operator (¡╣).  These extensions
were trivial to add to the calculator and extend its usefulness.  This example
also shows a variety of number formats: integer, floating point, and scientific
notation.

The default settings for the calculator give floating point number results.  If
you want to fix the decimal point, just type `DEC 2', for example, to set the
number of decimal points to two digits.  To restore to floating point format,
type `DEC 0'.  To toggle between floating point and scientific notation type
`SCI'.

Experiment on your own with the calculator to see how it handles various errors
like illegal characters and mismatched brackets.  If you have a Modula-2
compiler, attempt some extensions to the calculator, to recognize additional
mathematical constants like the base of the natural logarithm (e) or attempt a
cubed (x│) operator.


Summary

This article introduced a new floating point number system called ExNumbers
which solve some problems inherent in the IEEE floating point numbers used in
the Amiga.  I briefly described several utility functions which help to
manipulate ExNumbers and then explained how the basic mathematical operations
of addition, subtraction, multiplication, and division were implemented.  As a
prelude to introducing the calculator, I showed how ExNumbers are converted
into strings and conversely how strings are translated into ExNumbers.  I then
described the calculator program and demonstrated several features of the
CLI calculator.

In the next article I'll add an ExInteger module which gives us 172-bit logical
operations (AND, OR, XOR, BIT, SHIFTs) and base conversion functions.  As well,
an ExMathLib0 module will be introduced which uses the Amiga's coprocessor to
give ExNumber calculations with exponential, power, trigonometric, and
logarithmic functions.  All these new operators and functions will be
integrated into an improved CLI calculator which should be comparable to
commercial products.